import java.util.PriorityQueue;

class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null ; 
        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1 , o2) -> o1.val-o2.val) ;
        for(ListNode node : lists){
            if(node != null)
            queue.offer(node) ; 
        }
        ListNode newHead = new ListNode() ;
         ListNode last = newHead ;
        while(!queue.isEmpty()){
            ListNode cur = queue.poll() ;
             last.next = cur ;
             last = last.next ;
             if(cur.next != null){
                queue.offer(cur.next) ; 
             }
        }
        return newHead.next ;
    }
}